<mathematics, programming> When a function (or procedure) calls itself. Such a function is called "recursive". If the call is via one or more other functions then this group of functions are called "mutually recursive". If a function will always call itself, however it is called, then it will never terminate. Usually however, it first performs some test on its arguments to check for a "base case" - a condition under which it can return a value without calling itself. The canonical example of a recursive function is factorial: factorial 0 = 1 factorial n = n * factorial (n-1) Functional programming languages rely heavily on recursion, using it where a procedural language would use iteration. See also recursion, recursive definition, tail recursion. [Jargon File] (1996-05-11)

Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic.

recursion

<programming> When the last thing a function (or procedure) does is to call itself. Such a function is called tail recursive. A function may make several recursive calls but a call is only tail-recursive if the caller returns immediately after it. E.g. f n = if n < 2 then 1 else f (f (n-2) + 1) In this example both calls to f are recursive but only the outer one is tail recursive. Tail recursion is a useful property because it enables {tail recursion optimisation}. If you aren't sick of them already, see recursion and {tail recursion}. [Jargon File] (2006-04-16)

<programming, compiler> A generalisation of tail recursion introduced by D.H.D. Warren. It applies when the last thing a function does is to apply a constructor functions (e.g. cons) to an application of a non-primitive function. This is transformed into a tail call to the function which is also passed a pointer to where its result should be written. E.g. f [] = [] f (x:xs) = 1 : f xs is transformed into (pseudo C/Haskell): f [] = [] f l = f' l allocate_cons f' [] p = { *p = nil; return *p } f' (x:xs) p = { cell = allocate_cons; *p = cell; cell.head = 1; return f' xs &cell.tail } where allocate_cons returns the address of a new cons cell, *p is the location pointed to by p and &c is the address of c. [D.H.D. Warren, DAI Research Report 141, University of Edinburgh 1980]. (1995-03-06)

The Britto–Cachazo–Feng–Witten recursion relations are a set of on-shell recursion relations in quantum field theory. They are named for their creators, Ruth Britto, Freddy Cachazo, Bo Feng and Edward Witten.

Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3).